class Solution {
    vector<string> ret;
    string path;
    void dfs(int n)
    {
        if(path.size() == n)
        {
            ret.push_back(path);
            return;
        }
    
        if(!path.empty() && path.back() == '0')
            goto flag;
        path += "0";
        dfs(n);
        path.pop_back();

        flag:
        path += "1";
        dfs(n);
        path.pop_back();
    }
public:
    vector<string> validStrings(int n) {
        // 利用二进制位运算
        int mask = (1 << n) - 1;
        // [0, 2 ^ n - 1]
        for(int i = 0; i < (1 << n); i++)
        {
            int x = mask ^ i;   // x 相当于 i 取反后的结果
            if((x >> 1 & x) == 0)
            {
                // 有效字符串，不含相邻 1，说明 i 中不含相邻的 0
                // 下面截取 i 的低 n 位，可以使用一些api处理
                // string path;
                // x ^= mask;      // 下面需要用到 i 所以利用 x ，再 ^mask 就恢复了
                // for(int j = 0; j < n; j++)
                // {
                //     path = to_string(x % 2) + path;
                //     x /= 2;
                // }
                // ret.push_back(path);

                // ret.push_back(bitset<18>(x).to_string().substr(18 - n));
                ret.push_back(bitset<18>(x ^ mask).to_string().substr(18 - n));
            }
        }
        return ret;


        // 回溯写法
        // dfs(n);
        // return ret;
    }
};